package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         120,
		Discription: "三角形自顶向下路径最小和",
		Level:       2,
		Labels: map[string]int{
			"动态规划": 1,
			"空间复用": 1,
		},
	})
}

func MinimumTotal(triangle [][]int) int {
	h := len(triangle)
	dp := make([]int, h)
	dp[0] = triangle[0][0]
	//每行从左往右
	for i := 1; i < h; i++ {
		//最右边优先单独处理
		dp[i] = dp[i-1] + triangle[i][i]
		for j := i - 1; j >= 1; j-- {
			dp[j] = min(dp[j], dp[j-1]) + triangle[i][j]
		}
		//最左边最后单独处理，必须最后处理！
		dp[0] += triangle[i][0]
	}

	min := dp[0]
	for j := 1; j < h; j++ {
		if dp[j] < min {
			min = dp[j]
		}
	}

	return min
}